import collections

# 定义字典树节点（TrieNode）
class TrieNode:
    # Initialize your data structure here.
    def __init__(self):
        """
        初始化字典树节点。
        每个节点包含：
        - children: 一个 defaultdict，用来存储子节点，默认值为新的 TrieNode。
        - is_word: 一个布尔值，表示该节点是否是一个有效单词的结尾。
        """
        """
        在字典树（Trie）的实现中，children 是一个字典，它的键是字符（如字母），而值是 TrieNode 实例。字典树的每个节点都可能有多个子节点。
        collections.defaultdict(TrieNode) 的作用是，当访问一个不存在的字符时，它会自动创建一个新的 TrieNode 实例，而不是抛出 KeyError 错误。
        这对于字典树的构建非常方便，因为每当我们插入一个新字符时，我们无需显式检查该字符是否已经存在于字典中。如果不存在，defaultdict 会自动创建一个新的节点。
        """
        self.children = collections.defaultdict(TrieNode) # 用 defaultdict 方便自动创建子节点
        self.is_word = False # 默认该节点不是一个单词的结尾

# 定义字典树（Trie）类
class Trie:
    def __init__(self):
        """
        初始化字典树。
        字典树的根节点是一个 TrieNode。
        """
        self.root = TrieNode() # 根节点是一个空节点，没有任何字符

    def insert(self, word):
        """
        向字典树中插入一个单词。
        :param word: 要插入的单词
        """
        current = self.root # 从根节点开始插入
        for letter in word:
            # 如果字典树中当前节点没有这个字母，则会自动创建一个新的 TrieNode。
            current = current.children[letter]
        current.is_word = True # 最后一个字母节点标记为有效单词的结尾

    def search(self, word):
        """
        查找字典树中是否存在一个完整的单词。
        :param word: 要查找的单词
        :return: 如果该单词存在于字典树中，返回 True，否则返回 False
        """
        current = self.root  # 从根节点开始查找
        for letter in word:
            # 如果当前节点没有该字母的子节点，表示单词不存在
            current = current.children.get(letter)
            if current is None:
                return False # 提前返回 False，说明该字母不存在
        return current.is_word # 最后检查该节点是否是一个有效单词的结尾

    def startsWith(self, prefix):
        """
        查找字典树中是否有以给定前缀开始的单词。
        :param prefix: 要查找的前缀
        :return: 如果存在以该前缀开始的单词，返回 True，否则返回 False
        """
        current = self.root # 从根节点开始查找
        for letter in prefix:
            # 如果当前节点没有该字母的子节点，表示没有以该前缀开始的单词
            current = current.children.get(letter)
            if current is None:
                return False # 提前返回 False，表示没有匹配的前缀
        return True # 如果所有字母都匹配，表示前缀存在

    def enumerateMatch(self, word, space="_", backward=False):  # space=‘’
        """
        枚举字典树中与给定单词匹配的子串，返回所有以字母为前缀的匹配结果。
        :param word: 要匹配的单词 list
        :param space: 用于连接匹配的字母的字符（默认为“_”）
        :param backward: 是否从后向前枚举匹配（默认为 False，从前向后枚举）
        :return: 一个列表，包含所有匹配的子串
        """
        matched = [] # 存储所有匹配的子串
        # 如果 backward 为 False，则从前向后枚举匹配
        while len(word) > 0:
            if self.search(word):  # 如果该子串在字典树中是一个有效的单词
                matched.append(space.join(word[:])) # 将当前匹配的子串添加到结果列表中
            del word[-1] # 匹配下一个单词
        return matched
